/*
 * @lc app=leetcode.cn id=25 lang=cpp
 * @lcpr version=30204
 *
 * [25] K 个一组翻转链表
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x, next(next)) {}
 * };
 */
class Solution
{
public:
    ListNode *reverseKGroup(ListNode *head, int k)
    {
        if (!head || k <= 1)
            return head; // 特殊情况处理

        // 方法一：
        // 创建一个虚拟头节点，方便处理
        // ListNode dummy(0);
        // dummy.next = head;
        // ListNode* prevGroupEnd = &dummy; // 上一组的结尾节点

        // while (true) {
        //     // 找到当前组的起点和终点
        //     ListNode* groupStart = prevGroupEnd->next;
        //     ListNode* groupEnd = prevGroupEnd;
        //     for (int i = 0; i < k; ++i) {
        //         groupEnd = groupEnd->next;
        //         if (!groupEnd) return dummy.next; // 剩余节点不足 k 个，直接返回
        //     }

        //     // 保存下一组的起点
        //     ListNode* nextGroupStart = groupEnd->next;

        //     // 翻转当前组
        //     reverse(groupStart, groupEnd);

        //     // 连接翻转后的子链表
        //     prevGroupEnd->next = groupEnd;
        //     groupStart->next = nextGroupStart;

        //     // 更新 prevGroupEnd 为当前组的结尾
        //     prevGroupEnd = groupStart;

        // 方法二
        // 先求得链表长度
        ListNode *tmp = head;
        int n = 0;
        while (tmp)
        {
            n++;
            tmp = tmp->next;
        }

        ListNode dummy(0);
        dummy.next = head;
        ListNode *prevgroupend = &dummy;

        while (n >= k)
        {
            n -= k;

            // 翻转当前组
            ListNode *prev = nullptr;
            ListNode *cur = prevgroupend->next;
            ListNode *next = nullptr;
            for (int i = 0; i < k; ++i)
            {
                next = cur->next; // 更新 next
                cur->next = prev;
                prev = cur;
                cur = next;
            }

            // 连接翻转后的子链表
            ListNode *groupStart = prevgroupend->next; // 当前组的起点
            groupStart->next = next;                   // 当前组的尾节点连接到下一组的起点
            prevgroupend->next = prev;                 // 上一组的尾节点连接到当前组的头节点
            prevgroupend = groupStart;                 // 更新 prevgroupend 为当前组的尾节点
        }

        return dummy.next;

        // 方法三：
        // // 检查链表是否有足够的节点进行翻转
        // ListNode* cur = head;
        // for (int i = 0; i < k; ++i) {
        //     if (!cur) return head; // 剩余节点不足 k 个，直接返回
        //     cur = cur->next;
        // }

        // // 翻转当前组的 k 个节点
        // ListNode* prev = nullptr;
        // ListNode* next = nullptr;
        // cur = head;
        // for (int i = 0; i < k; ++i) {
        //     next = cur->next;
        //     cur->next = prev;
        //     prev = cur;
        //     cur = next;
        // }

        // // 递归处理剩余部分，并连接
        // head->next = reverseKGroup(cur, k);

        // // 返回翻转后的头节点
        // return prev;
    }
    // private:
    //     // 翻转链表的一部分，从 start 到 end
    //     void reverse(ListNode* start, ListNode* end) {
    //         ListNode* prev = nullptr;
    //         ListNode* cur = start;
    //         ListNode* stop = end->next; // 翻转到 end 为止
    //         while (cur != stop) {
    //             ListNode* next = cur->next;
    //             cur->next = prev;
    //             prev = cur;
    //             cur = next;
    //         }
};
// @lc code=end

/*
// @lcpr case=start
// [1,2,3,4,5]\n2\n
// @lcpr case=end

// @lcpr case=start
// [1,2,3,4,5]\n3\n
// @lcpr case=end

 */
